\documentclass[a4paper]{article}

% \usepackage{a4wide}

\usepackage{amsmath}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[pdftex]{graphicx}
\usepackage{longtable}
\usepackage{hyperref}
\usepackage[portuguese]{babel}
\usepackage{float}
\usepackage{listings}
\usepackage{makeidx}  % allows for indexgeneration
\usepackage{times}
\usepackage{pdfpages}
\usepackage{tikz}
\usepackage{pifont}
\usepackage[all]{xy}
\usepackage[center]{caption}


\lstset{
language=Java,
breaklines=true,                % sets automatic line breaking
breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
captionpos=b,                   % sets the caption-position to bottom
frame=shadowbox,
}

\newcommand{\lstJava}[1]{\lstinline[language=Java]{#1}}
% So para ser mais simples de usar
\newcommand{\todo}[1]{\marginpar{#1}}
\newcommand{\chone}[0]{\ding{172}}
\newcommand{\OO}[1]{{\cal O}(#1)}

\renewcommand\lstlistingname{Listagem}
\renewcommand\lstlistlistingname{Listagens}

\addto\captionsportuguese{\renewcommand{\refname}{Recursos}}


%\renewcommand{\bibname}{foobar}

\begin{document}

%\setcounter{page}{2}

\includepdf{rostoRF.pdf}

\section*{Objectivo}

Este trabalho têm como objectivo criar uma implementação, em
Java, do jogo Hex.

Esta implementação servirá como um suporte prático para melhorar a
aprendizagem de conceitos apresentados nas aulas teóricas da
disciplina, nomeadamente as estratégias de pesquisa considerando
adversários. Em especial, este trabalho serviu para um estudo do
algoritmo Minimax com cortes Alfa-Beta.

Para facilidade de utilização do programa, foi também desenvolvida
duas interfaces para o jogo: uma interface em modo de texto e uma
interface gráfica utilizando a API Swing do Java.

Para finalizar, foram também adicionadas várias características para
melhorar a qualidade do jogo, tais como diferentes modos de jogo,
diferentes modos de dificuldade e diferentes tamanhos de tabuleiro.

\section*{Descrição}

\subsection*{Funcionalidades}

O programa desenvolvido neste trabalho contêm várias funcionalidades
tais como a escolha do tamanho do tabuleiro no qual irá ser efectuado
o jogo.

Existem também três tipos de jogo disponíveis:

\begin{itemize}
\item Humano contra Humano
\item Humano contra Computador
\item Computador contra Computador
\end{itemize}

É também possível modificar a dificuldade da inteligência
artificial, tendo que conta que o único parâmetro diferente entre as
várias dificuldades é o nível de profundidade do algoritmo Minimax que 
é usado. Dito isto, as três dificuldades existentes são:

\begin{itemize}
\item Fácil, correspondendo ao algoritmo Minimax com profundidade 2
\item Médio, correspondendo ao algoritmo Minimax com profundidade 3
\item Difícil, correspondendo ao algoritmo Minimax com profundidade 4
\end{itemize}

Em termos de código, a variáveis que determinam a profundidade do
algoritmo Minimax para cada dificuldade encontram-se no ficheiro
$ComputerAI.java$, sendo elas:

\begin{lstlisting}[frame=none]
  static private final int EASY_DEPTH = 2;
  static private final int MEDIUM_DEPTH = 3;
  static private final int HARD_DEPTH = 4;
\end{lstlisting}

\subsection*{Estrutura do programa}

O programa desenvolvido encontra-se dividido em vários módulos,
estando estes sepa\-rados por ficheiros de código Java.

O módulos desenvolvidos foram os seguintes:

\begin{itemize}
\item \emph{Hex} -- Ponto de entrada do programa. Contêm a função \emph{main}
  do programa;
\item \emph{HexConsole} -- Módulo da interface de consola;
\item \emph{HexGraphical} -- Módulo da interface em modo gráfico;
\item \emph{Board} -- Módulo do tabuleiro de jogo. Contêm o algoritmo para
  detectar ca\-minhos no mesmo;
\item \emph{ComputerAI} -- Módulo da inteligência artificial.
\end{itemize}

As relações entre estes módulos podem ser vistos na figura
\ref{fig:diagrama_de_modulos}, onde as setas apontam para os módulos
que um determinado módulo utiliza.

\begin{figure}[h!]
  \begin{center}
    \input{diagrama_de_modulos.tex}    
  \end{center}
  \caption{Diagrama dos módulos do programa e as suas relações}
  \label{fig:diagrama_de_modulos}
\end{figure}

\subsection*{Esquemas de Representação de Conhecimento}

\subsection*{Análise da complexidade dos algoritmos usados}

Nesta secção será analisada a complexidade dos dois algoritmos mais
importantes do programa, o \emph{checkLineThroughBoard} da classe
\emph{Board}, que permite detectar um ca\-minho que percorra um
tabuleiro do topo ao fundo do mesmo, e o
\emph{calculateBoardHeuristicValue} da classe \emph{ComputerAI} que
atribui valores a tabuleiros, sendo esses va\-lores depois usados no
algoritmo Minimax com cortes Alfa-Beta.

\subsubsection*{Board.checkLineThroughBoard}

Devido ao polimorfismo da linguagem Java, existem três funções com o
nome \emph{checkLineThroughBoard} na classe \emph{Board}.

Para ser possível diferenciar entre elas, cada função será numerada:

\begin{dingautolist}{192}
\item -- checkLineThroughBoard(int[][] boardToCheck, int color)
\item -- checkLineThroughBoard(int[][] boardToCheck, int y, int x, int color)
\item -- checkLineThroughBoard(int[][] boardToCheck, int y, int x, int color, List<int[]> passedPositions)
\end{dingautolist}
A função \ding{172} encontra-se dividida em duas partes.

O primeiro ciclo \emph{for}, mostrado na listagem \ref{lst:for1},
serve para verificar em existe pelo menos uma peça da cor pedida em
cada linha do tabuleiro. Caso isso não ocorra, não pode haver um
caminho que vá do topo do tabuleiro até ao fundo do mesmo.

\begin{lstlisting}[caption=O primeiro ciclo \emph{for} da função \ding{172},label=lst:for1]
for (int[] boardLine : boardToCheck) {
    boolean existsColoredPiece = false;

    for (int boardPlace : boardLine) {
        if (boardPlace == color) {
            existsColoredPiece = true;
        }
    }

    if (!existsColoredPiece) {
        return false;
    }
}
\end{lstlisting}

Facilmente se mostra que este código tem uma complexidade $\OO{n^2}$:

\begin{align*}
n*(1+n*(1+1)+1+1) =&\\
n*(1+2n+2) =&\\
n*(2n+3) =&\\
2n^2+3n \rightarrow & \OO{n^2}\\
\end{align*}

O resto da função \ding{172}, (ver código da listagem \ref{lst:for2}),
chama a função \ding{173} para cada elemento do topo do tabuleiro para
tentar descobrir caminhos que começam nesse elemento e conseguem
atingir o fundo do tabuleiro.

\begin{lstlisting}[caption=O segundo ciclo \emph{for} da função \ding{172},label=lst:for2] 
for (int x = 0; x != boardToCheck[0].length; x++) {
    if (boardToCheck[0][x] == color) {
        if (checkLineThroughBoard(boardToCheck, 0, x, color)) {
            return true;
        }
    }
}
\end{lstlisting}

Observa-se que a complexidade deste código é $\OO{n*\text{\ding{173}}}$.

A função \ding{173} simplesmente cria uma lista vazia (do tipo
\emph{LinkedList}) que servirá para armazenar as posições do tabuleiro
que a função \ding{174} irá processar, para impedir que a função
\ding{174} entre em ciclo infinito.

A função \ding{174} é uma função recursiva. Como tal teremos de
começar a análise da sua complexidade pelo seu caso-base, que pode ser
visto na listagem \ref{lst:basecase}.

\begin{lstlisting}[caption=Caso-base da função \ding{174},label=lst:basecase]
// Final do passo recursivo: Chegar ao fundo do tabuleiro
if (y == boardToCheck.length-1)
    return true;
\end{lstlisting}

Facilmente se vê que esta parte do código tem uma complexidade $\OO{1}$.

A parte recursiva da função envolve a procura de peças que estejam
adjacentes à casa que está a ser analisada que tenham a mesma cor e
que não estejam presentes na lista \emph{passedPositions}.

Essa parte recursiva requer o uso de uma função auxiliar
\emph{listContainsBoardPlace} uma lista de posições do tabuleiro
\emph{list} e uma posição do tabuleiro \emph{boardPlace} e verifica se
\emph{boardPlace} está contido em \emph{list}. Esta função tem uma
complexidade $\OO{n}$, pois tem de percorrer a lista \emph{list} apenas
uma vez.

O algoritmo recursivo da função \ding{174} (código na listagem
\ref{lst:parteRecursiva}) simplesmente \mbox{chama-se} a si mesma para as
casas que se encontram à esquerda, direita, baixo e diagonal baixo
esquerda, desde que essas casas tenham a mesma cor que a da casa
actual. Este comportamento pode ser visto na figura
\ref{fig:algoRecursivo}.

\begin{figure}[h!]
    \begin{displaymath}
      \xymatrix{
        4 & X \ar[l] \ar[r] \ar[dl] \ar[d] & 2 \\
        3 & 1
      }
    \end{displaymath}
    \caption{As casas que são visitadas recursivamente pela função
      \ding{174}. Os números indicam a ordem de visita.}
    \label{fig:algoRecursivo}
\end{figure}

\begin{lstlisting}[caption=Parte recursiva do algoritmo \ding{174},label=lst:parteRecursiva]
if (boardToCheck[y+1][x] == color) {
    int[] boardPlace = {y+1, x};

    if (!listContainsBoardPlace(passedPositions, boardPlace)) {
        passedPositions.add(boardPlace);

        if (checkLineThroughBoard(boardToCheck, boardPlace[0], boardPlace[1], color, passedPositions)) {
            return true;
        }
    }
}
if (x != boardToCheck[0].length-1 && boardToCheck[y][x+1] == color) {
    int[] boardPlace = {y, x+1};

    if (!listContainsBoardPlace(passedPositions, boardPlace)) {
        passedPositions.add(boardPlace);

        if (checkLineThroughBoard(boardToCheck, boardPlace[0], boardPlace[1], color, passedPositions)) {
            return true;
        }
    }
}
if (x != 0 && boardToCheck[y+1][x-1] == color) {
    int[] boardPlace = {y+1, x-1};

    if (!listContainsBoardPlace(passedPositions, boardPlace)) {
        passedPositions.add(boardPlace);
    
        if (checkLineThroughBoard(boardToCheck, boardPlace[0], boardPlace[1], color, passedPositions)) {
            return true;
        }
    }
}
if (x != 0 && boardToCheck[y][x-1] == color) {
    int[] boardPlace = {y, x-1};

    if (!listContainsBoardPlace(passedPositions, boardPlace)) {
        passedPositions.add(boardPlace);

        if (checkLineThroughBoard(boardToCheck, boardPlace[0], boardPlace[1], color, passedPositions)) {
            return true;
        }
    }
}
\end{lstlisting}

Na análise do algoritmo recursivo, considera-se que $S$ corresponde ao
tamanho do tabuleiro que está a ser analisado e que $F$ corresponde à
função \ding{174}, que recebe um tuplo $(n,m)$ em que $n$ corresponde
a uma posição $y$ do tabuleiro e $m$ corresponde a uma posição $x$ do
tabuleiro. $F$ recebe também um conjunto $l$ que contêm os tuplos
$(n,m)$ que já foram visitados.

Desta forma, a complexidade da função \ding{174} é:

\begin{align*}
  F(S-1, m, l) = &\, \OO{1} \text{\hspace{2em} $\longleftarrow$ O caso base}\\
  F(n, m, l) = &\, \OO{F(n+1,m,l)} \text{\hspace{1em}sse\hspace{1em}} (n+1,m) \notin l \\
               &\, + \OO{F(n,m+1,l)} \text{\hspace{1em}sse\hspace{1em}} (n,m+1) \notin l\\
               &\, + \OO{F(n+1,m-1,l)} \text{\hspace{1em}sse\hspace{1em}} (n+1,m-1) \notin l\\
               &\, + \OO{F(n,m-1,l)} \text{\hspace{1em}sse\hspace{1em}} (n,m-1) \notin l\\
  F(n, 0, l) = &\, \OO{F(n+1,m,l)} \text{\hspace{1em}sse\hspace{1em}} (n+1,m) \notin l\\
               &\, + \OO{F(n,m+1,l)} \text{\hspace{1em}sse\hspace{1em}} (n,m+1) \notin l\\
  F(n, S-1, l) = &\, \OO{F(n+1,S-1,l)} \text{\hspace{1em}sse\hspace{1em}} (n+1,S-1) \notin l\\
                 &\, + \OO{F(n+1,S-2,l)} \text{\hspace{1em}sse\hspace{1em}} (n+1,S-2) \notin l\\
                 &\, + \OO{F(n,S-2,l)} \text{\hspace{1em}sse\hspace{1em}} (n,S-2) \notin l\\
\end{align*}

\subsubsection*{ComputerAI.calculateBoardHeuristicValue}

O algoritmo \emph{calculateBoardHeuristicValue} atribui valores aos
tabuleiros gerados pelo algoritmo Minimax com cortes Alfa-Beta.

O protótipo desta função é:

\begin{lstlisting}[frame=none]
int calculateBoardHeuristicValue(Board board, int player)
\end{lstlisting}
%
onde \emph{board} representa o tabuleiro a ser pontuado e
\emph{player} representa o jogador maximizante do algoritmo Minimax
com cortes Alfa-Beta.

Esta função toma em conta quatros situações:

\begin{itemize}
\item Se o tabuleiro termina o jogo;
\item Se existem peças nos cantos com ângulos agudos do tabuleiro;
\item Se existe uma peça no centro do tabuleiro;
\item O número de ``duas pontes''\cite{hexwiki_two_bridge} existentes
  para cada jogador.
\end{itemize}

Para a primeira situação são definidos dois valores, o
\emph{boardValueWin} e o \emph{board\-ValueLose}.

Este valores são usados no código da listagem \ref{lst:valuefirst}
para atribuir valores ao tabuleiro dependendo do valor do argumento
\emph{player} e de quem é que ganharia o jogo.

\begin{lstlisting}[caption=Código responsável por pontuar os tabuleiros que terminam o jogo,label=lst:valuefirst]
if (player == Color.WHITE) {
    if (board.hasWhiteWon())
        boardValue += boardValueWin;
    else if (board.hasBlackWon())
        boardValue -= boardValueLose;
} else {
    if (board.hasBlackWon())
        boardValue += boardValueWin;
    else if (board.hasWhiteWon())
        boardValue -= boardValueLose;
}
\end{lstlisting}

As funções \emph{Board.hasWhiteWon} e \emph{Board.hasBlackWon} estão
definidas no ficheiro \emph{Board.java} e o seu código pode ser visto
na listagem \ref{lst:boardterminajogo}:

\begin{lstlisting}[caption=Código que permite ver se um jogador de determinada cor ganhou o jogo,label=lst:boardterminajogo]
public boolean hasWhiteWon() {
    return checkLineThroughBoard(transposeBoard(),
        Color.WHITE);
}

public boolean hasBlackWon() {
    return checkLineThroughBoard(board, Color.BLACK);
}
\end{lstlisting}

A função \emph{checkLineThroughBoard} já foi analisada anteriormente,
no entanto a função \emph{transposeBoard} ainda não foi analisada.

O código da função \emph{transposeBoard} pode ser vista na listagem
\ref{lst:transposeBoard}.

\begin{lstlisting}[caption=Código do transposeBoard,label=lst:transposeBoard]
private int[][] transposeBoard() {
    int[][] transposed = new int[board[0].length][board.length];
    
    for(int rows = 0; rows < board.length; rows++){
        for(int cols = 0; cols < board[0].length; cols++){
            transposed[cols][rows] = board[rows][cols];
        }
    }

    return transposed;
}
\end{lstlisting}

É trivial observar que a complexidade do algoritmo de
\emph{transposeBoard} é $\OO{n^2}$

Assumindo que $C$ representa a complexidade do algoritmo
\emph{checkLineThroughBoard}, observa-se que a complexidade de
\emph{hasWhiteWon} é $\OO{n^2 + C}$ e a de \emph{hasBlackWon} é
$\OO{C}$.

Retornando ao código da listagem \ref{lst:valuefirst}, observa-se que
o pior caso irá ocorrer quando o argumento \emph{board} tiver um
tabuleiro em que nenhum dos jogadores vença, independentemente do
valor do argumento \emph{player}, pois será necessário chamar ambas as
funções \emph{hasWhiteWon} e \emph{hasBlackWon} para verificar que
nenhum dos jogadores ganha.

Portanto, a complexidade ${\cal O}$ desse código será $\OO{n^2 + C +
  C}$ o que corresponde a $\OO{n^2 + C}$, em que $n$ representa o
tamanho do tabuleiro \emph{board}.

Após este cálculo, o algoritmo \emph{calculateBoardHeuristicValue}
atribui pontuações dependendo do número de peças existentes no cantos
com ângulos agudos.

Para isso utiliza uma função auxiliar
\emph{numberOfPiecesInSharpCorners} com o seguinte protótipo:

\begin{lstlisting}[frame=none]
int numberOfPiecesInSharpCorners(Board board, int player)
\end{lstlisting}
onde \emph{board} representa o tabuleiro a ser analisado e \emph{player}
representa o jogador cujas peças vão ser contadas.

A figura \ref{fig:cantosAgudos} mostra o que se pretende dizer com
``cantos com ângulos agudos''. A razão para se evitar estes cantos, é
que as peças colocadas nessas posições ficam só duas casas adjacentes.

\begin{figure}[h!]
  \begin{center}
    \input{cantos_agudos.tex}    
  \end{center}
  \caption{Tabuleiro 3x3 com os cantos com ângulos agudos assinalados}
  \label{fig:cantosAgudos}
\end{figure}

O código completo da função pode ser visto na listagem
\ref{lst:funcaoCantosAgudos}, onde facilmente se observa que a
complexidade do algoritmo usado é $\OO{1}$.

\begin{lstlisting}[caption=Código da função que devolve o número de
  peças nos cantos agudos de um jogador,label=lst:funcaoCantosAgudos]
static private int numberOfPiecesInSharpCorners(Board board, int player) {
    int piecesInCorner = 0;

    if (board.getBoard()[0][0] == player)
        piecesInCorner++;
    if (board.getBoard()[board.getSize()-1][board.getSize()-1] == player)
        piecesInCorner++;

    return piecesInCorner;
}
\end{lstlisting}

De seguida a função \emph{calculateBoardHeuristicValue} determina se a
casa central do tabuleiro se encontra disponível. Apesar de esta casa
só poder existir em tabuleiros com tamanho ímpar, esta é uma casa
importante, como é dito em \cite{hexwiki_center}:

\begin{quotation}
  Playing the first move in the center is arguably the strongest
  opening in Hex. However, due to the swap rule, it is in fact one of
  the weakest.
\end{quotation}

Como este programa não implementa a regra de troca
\cite{hexwiki_swap}, é quase sempre vantajoso para o computador
colocar uma peça nessa posição o mais cedo possível. O código da
listagem \ref{lst:valueThird} tem a conta essa situação. É fácil de
observar, após a leitura das funções \emph{Board.getSize} e
\emph{Hex.otherPlayer} na listagem \ref{lst:getsizeotherplayer}, que a
complexidade deste código é $\OO{1}$.

\begin{lstlisting}[caption=Código das funções Board.getSize e
  Hex.otherPlayer. Ambas as funções têm uma complexidade $\OO{1}$.,label=lst:getsizeotherplayer]
public int getSize() {
    return board.length;
}

public static int otherPlayer(int player) {
    if(player == Color.WHITE)
        return Color.BLACK;
    else
        return Color.WHITE;
}
\end{lstlisting}


\begin{lstlisting}[caption=Código de
  \emph{calculateBoardHeuristicValue} que faz com que a IA tente
  colocar peças no centro dos tabuleiros de tamanhos ímpares,label=lst:valueThird]
int centerLine = board.getSize()/2;
int centerColumn = board.getSize()/2;

if ((board.getSize() % 2) == 1) {
    if (board.getBoard()[centerLine][centerColumn] == player)
        boardValue += 1000;
    else if (board.getBoard()[centerLine][centerColumn] == Hex.otherPlayer(player))
        boardValue -= 1000;
}
\end{lstlisting}

Por fim, a função \emph{calculateBoardHeuristicValue} tenta aumentar o
número de ``duas pontes'' \cite{hexwiki_two_bridge} existentes que
pertençam ao jogador maximizante. A figura \ref{fig:two_bridges}
mostra porque é importante a criação de ``duas pontes''.

\begin{figure}[h!]
  \begin{center}
    \input{duas_pontes.tex}    
  \end{center}
  \caption{As ``duas pontes'' são importantes pois permitem a um
    jogador criar um caminho mesmo quando o seu oponente o tenta cortar}
  \label{fig:two_bridges}
\end{figure}

Para tal, existem duas funções auxiliares, \emph{numberOfTwoBridges} e
\emph{countNumberOf\-TwoBridgesFromPosition}, cujos protótipos são:

\begin{lstlisting}[frame=none]
int numberOfTwoBridges(Board board, int player)
int countNumberOfTwoBridgesFromPosition(Board board, int line, int column, int player)
\end{lstlisting}
onde \emph{board} representa o tabuleiro a ser analisado,
\emph{player} representa o jogador ao qual se vai contar as ``duas
pontes'', \emph{line} representa uma linha do tabuleiro \emph{board} e
\emph{column} representa uma coluna do tabuleiro \emph{board}.

A função \emph{countNumberOfTwoBridgesFromPosition} só é chamada a
partir da função \emph{numberOfTwoBridges} por isso iremos começar a
análise da complexidade por ela.

A função \emph{countNumberOfTwoBridgesFromPosition} necessita primeiro
de aumentar o tamanho do tabuleiro em duas unidades e colocar nesses
limites peças das cores correspondentes à cor do jogador que pode
fazer caminhos nesses limites (ver figura \ref{fig:tabuleiromaior})
para que o algoritmo também tenha em conta o limites do tabuleiro ao
contar as ``duas pontes'' existentes.

O código que faz isto encontra-se na listagem
\ref{lst:twobriges1}. Pode-se ver que, apesar de extenso, o código é a
grande maioria dele \emph{if}s que utilizam o código do
\emph{Board.placePiece} e da classe \emph{Move}. Estes podem ser
vistos, respectivamente, na listagem \ref{lst:placePiece} e
\ref{lst:Move} e ambos têm uma complexidade $\OO{1}$.

Assim, o código da listagem \ref{lst:twobriges1} tem uma complexidade
de $\OO{n^2}$.

\begin{lstlisting}[caption=O código da função
  \emph{countNumberOfTwoBridgesFromPosition} que cria o tabuleiro extra,label=lst:twobriges1]
int[][] internalRepresentation = board.getBoard();
int temporaryBoardSize = board.getSize() + 2;

Board temporaryBoard = new Board(temporaryBoardSize);

for (int tempLine = 0; tempLine != temporaryBoardSize; tempLine++) {
    for (int tempColumn = 0; tempColumn != temporaryBoardSize; tempColumn++) {
        // Canto superior esquerdo
        if (tempLine == 0 && tempColumn == 0) {
            temporaryBoard.placePiece(Color.WHITE, new Move(0, 0));
        }
        // Canto inferior esquerdo
        else if (tempLine == temporaryBoardSize-1
                 && tempColumn == 0) {
            temporaryBoard.placePiece(Color.WHITE, new Move(tempLine, 0));
        }
        // Canto superior direito
        else if (tempLine == 0
                 && tempColumn == temporaryBoardSize-1) {
            temporaryBoard.placePiece(Color.BLACK, new Move(0, tempColumn));
        }
        // Canto inferior direito
        else if (tempLine == temporaryBoardSize-1
                 && tempColumn == temporaryBoardSize-1) {
            temporaryBoard.placePiece(Color.BLACK, new Move(tempLine, tempColumn));
        }
        // Linha superior ou linha inferior
        else if (tempLine == 0
                 || tempLine == temporaryBoardSize-1) {
            temporaryBoard.placePiece(Color.BLACK, new Move(tempLine, tempColumn));
        }
        // Coluna da esquerda ou coluna da direita
        else if (tempColumn == 0
                 || tempColumn == temporaryBoardSize-1) {
            temporaryBoard.placePiece(Color.WHITE, new Move(tempLine, tempColumn));
        }
        // Pecas que vem do tabuleiro original
        else {
            // Converter tempLine e tempColumn para coordenadas do tabuleiro original
            int originalLine = tempLine - 1;
            int originalColumn = tempColumn - 1;
            temporaryBoard.placePiece(internalRepresentation[originalLine][originalColumn], new Move(tempLine, tempColumn));
        }
    }
}
\end{lstlisting}

\begin{lstlisting}[caption=O código de \emph{Board.placePiece},label=lst:placePiece]
public void placePiece(int colorPiece, Move move) {
    int[] boardLine = board[move.getLine()];
    boardLine[move.getColumn()] = colorPiece;
}
\end{lstlisting}

\begin{lstlisting}[caption=O código de \emph{Move} e 
  \emph{Move.getLine} e \emph{Move.getColumn},label=lst:Move]
public Move(int line, int column) {
    this.line = line;
    this.column = column;
}

public int getLine() {
    return line;
}

public int getColumn() {
    return column;
}
\end{lstlisting}

\begin{figure}[h!]
  \begin{center}
    \input{tabuleiro_maior.tex}    
  \end{center}
  \caption{Tabuleiro que \emph{countNumberOfTwoBridgesFromPosition}
    cria quando recebe um tabuleiro de 3x3. Os espaços em branco são
    preenchidos pelas peças originais do tabuleiro \emph{board}.}
  \label{fig:tabuleiromaior}
\end{figure}

Após criar o tabuleiro com o tamanho maior, o algoritmo simplesmente
verifica se existem duas casas livres entre a posição \emph{line} e
\emph{column} e as casas onde será possível fazer ``duas
pontes''. Esta parte do código tem uma complexidade $\OO{1}$.

Podemos então dizer que a complexidade da função
\emph{countNumberOfTwoBridgesFromPosition} é $\OO{n^2 + 1}$ ou seja,
$\OO{n^2}$.

Em relação ao código da função \emph{numberOfTwoBridges}, como se pode
observar pela listagem \ref{lst:numberbridges}, a sua complexidade é
$\OO{n^2*n^2}$, ou seja, $\OO{n^4}$ devido ao facto de a chamada à
função \emph{countNumberOfTwoBridgesFromPosition} estar dentro de dois
ciclos \emph{for}.

\mbox{}

\begin{lstlisting}[caption=Corpo da função \emph{numberOfTwoBridges},label=lst:numberbridges]
int numberOfTwoBridges = 0;
int[][] internalRepresentation = board.getBoard();
for (int line = 0; line != internalRepresentation.length; line++) {
    for (int column = 0; column != internalRepresentation[0].length; column++) {
        numberOfTwoBridges += countNumberOfTwoBridgesFromPosition(board, line, column, player);
    }
}
return numberOfTwoBridges;
\end{lstlisting}

Após a análise do código que trata das diferentes situações que a
função \emph{calculateBoardHeuristicValue} tem em conta, é agora
possível indicar qual a sua complexidade.

A tabela 1 mostra as situações que o algoritmo
\emph{calculateBoardHeuristicValue} toma em consideração, bem como as
respectivas complexidades desses algoritmos. Relembrando que $C$
corresponde à complexidade do algoritmo \emph{Board.checkLineThroughBoard},
a complexidade do algoritmo \emph{calculateBoardHeuristicValue} é
$\OO{n^2+C+1+1+n^4}$, o que dá $\OO{n^4+C}$.

\begin{table}[h!]
  \begin{tabular}{|c|c|}
    \hline
    Se o tabuleiro termina o jogo & $\OO{n^2+C}$ \\
    Se existem peças nos cantos com ângulos agudos do tabuleiro &
    $\OO{1}$ \\
    Se existe uma peça no centro do tabuleiro & $\OO{1}$ \\
    O número de duas pontes existentes para cada jogador & $\OO{n^4}$ \\
    \hline
  \end{tabular}
  \label{tab:calculatesituations}
  \caption{As várias situações que \emph{calculateBoardHeuristicValue}
    toma em consideração, bem como as complexidades dos algoritmos
    usados para as processar}
\end{table}


\subsection*{Ambiente de desenvolvimento}

Este trabalho foi realizado na linguagem de programação
Java \cite{java}, tendo o código sido desenvolvido e testado em
máquinas correndo o sistema operativo Ubuntu\cite{ubuntu}, usando o
compilador \emph{javac} e os ambientes de programação
Emacs \cite{emacs} e Netbeans\cite{netbeans}.

Foram usados também alguns pacotes extra de ``software'' que
permitiram melhorar a qualidade do código. Estes foram:

\begin{itemize}
  \item Sistema de cobertura de código Emma\cite{emma}
  \item Sistema de compilação de código Ant\cite{ant}
  \item Sistema de testes unitários Junit\cite{junit}
\end{itemize}

Para a entrega final do trabalho foi criado um ficheiro
Makefile\cite{make} para simplificar a compilação do programa e
a execução dos testes unitários realizados.

\subsection*{Avaliação do programa}

O programa foi testado de diversas formas, sendo sido usados
diferentes métodos para testar diferentes módulos do programa.

Os algoritmos de \emph{checkLineThroughBoard} e
\emph{calculateBoardHeuristicValue} foram testados com o jogo a testes
unitários, estando estes, respectivamente nos ficheiros
\emph{BoardTests.java} e \emph{ComputerAITests.java}.

Estes testes unitários foram escritos com o Junit\cite{junit}, que é
entregue juntamente com este relatório.

Por fim, as interfaces gráfica e em modo de texto foram testadas
através da sua utilização por parte de utilizadores.

\section*{Conclusões}
% Escreva aqui as conclusões que achar devidas. Diga como o programa
% poderia ser melhorado. Que funcionalidades adicionais deveria ter ou
% que sofisticações gostaria de ver implementadas caso tivesse tempo
% para tal. Como poderia aumentar a eficiência do programa, torná-lo
% mais rápido ou restringir os gastos de memória.

Tal como foi dito no relatório intercalar, o facto de o jogo Hex ser
um jogo com regras simples permitiu-nos concentrar na implementação e
estudo dos algoritmos de inteligência artificial.

No entanto, o programa ainda pode melhorado de diversas formas, sendo
a principal a melhoria da função heurística
\emph{calculateBoardHeuristicValue}, implementando mais algumas
estratégias descritas na HexWiki\cite{hexwiki}.

Seria também interessante testar a inteligência artificial
implementada neste programa contra outras que foram desenvolvidas para
jogar este jogo, como por exemplo, a desenvolvida para o programa
HEXY\cite{vadim}.

\begin{thebibliography}{99}

  \subsection*{Software}

\bibitem{java}
  Oracle,
  ``Oracle Technology Network for Java Developers'',
  2011,
  <\url{http://www.oracle.com/technetwork/java/index.html}>.

\bibitem{ubuntu}
  Canonical Ltd.,
  ``Homepage | Ubuntu'',
  2011,
  <\url{http://www.ubuntu.com}>.

\bibitem{emacs}
  Free Software Foundation,
  ``Emacs 23.2.1'',
  <\url{http://www.gnu.org/software/emacs}>.

\bibitem{netbeans}
  Oracle Corporation,
  ``Netbeans 7.0'',
  <\url{http://netbeans.org}>.

\bibitem{emma}
  Vlad Roubtsov,
  ``EMMA: a free Java code coverage tool'',
  2005,
  <\url{http://emma.sourceforge.net}>.

\bibitem{ant}
  The Apache Software Foundation,
  ``Apache Ant - Welcome'',
  2010,
  <\url{http://ant.apache.org}>.

\bibitem{junit}
  Object Mentor,
  ``Welcome to JUnit.org! | JUnit.org'',
  2011,
  <\url{http://www.junit.org}>.

\bibitem{make}
  Free Software Foundation,
  ``GNU Make'',
  <url{http://www.gnu.org/software/make}>.
  
% template  
% \bibitem{nome}
%   nome autor,
%   ``titulo'',
%   in \emph{nome publicacao}
%   ano publicacao, visto a _data_,
%   <\url{url}>

  \subsection*{Internet}

\bibitem{hexwiki_two_bridge}
  ``Basic (strategy guide) - HexWiki'',
  7 de Novembro de 2009, visto a 07/04/2011,
  <\url{http://www.hexwiki.org/index.php?title=Basic_%28strategy_guide%29#The_two-bridge}>.

\bibitem{hexwiki_center}
  ``Center opening - HexWiki'',
  12 de Dezembro de 2007, visto a 07/04/2011,
  <\url{http://www.hexwiki.org/index.php?title=Center_opening}>.

\bibitem{hexwiki_swap}
  ``Swap rule - HexWiki'',
  26 de Janeiro de 2008, visto a 07/04/2011,
  <\url{http://www.hexwiki.org/index.php?title=Swap_rule}>.

\bibitem{hexwiki}
  ``Main Page - Hexwiki'',
  3 de Março de 2009, visto a 07/04/2011,
  <\url{http://www.hexwiki.org/index.php?title=Main_Page}>.

\bibitem{vadim}
  Vadim V. Anshelevich,
  ``A hierarchical approach to computer Hex'',
  in \emph{Elsevier Science B.V},
  2002, visto a 15/05/2011,
  <\url{http://home.earthlink.net/~vanshel/VAnshelevich-ARTINT.pdf}>.


\end{thebibliography}


\section*{Anexos}

\appendix

\subsection*{Manual do utilizador}

Para facilitar a compilação do programa é fornecido um ficheiro
Makefile que define as seguintes opções:

\begin{itemize}
\item all - Compilar o código dos ficheiros Java e colocar os ficheiro
  \emph{.class} na pasta \emph{build}
\item run-tests - Compilar o código dos ficheiros Java e executar os
  testes unitários \emph{BoardTests} e \emph{ComputerAITests}
\item clean - Apagar a pasta \emph{build}
\end{itemize}

Portanto, após executar o comando \verb=make= bastará entrar na pasta
\emph{build} e executar o comando \verb=java Hex= para usar a
interface gráfica, ou \verb=java Hex -c= para utilizar a interface em
modo de texto.

Ou seja, os comandos a usar para compilar e executar a interface
gráfica são:

\begin{verbatim}
      make
      cd build
      java Hex
\end{verbatim}

Ao passo que para compilar e executar a interface em modo texto os
comandos são:

\begin{verbatim}
      make
      cd build
      java Hex -c
\end{verbatim}

Para executar os testes unitários basta executar o comando
\verb=make run-tests= na pasta raiz do projecto e para apagar os
ficheiros gerados durante a compilação do programa basta executar o
comando \verb=make clean=.

Para utilizar qualquer uma das interfaces basta seguir as instruções
indicadas no ecrã, bem como as imagens que aparecem na próxima secção
deste relatório.

\subsection*{Exemplo de uma execução}

\begin{figure}[h!]
  \begin{center}
    \includegraphics[width=0.80\textwidth]{screenshots/grafico/ss_menu_inicial.png}
  \end{center}
  \caption{O menu inicial do programa}
\end{figure}

\begin{figure}[h!]
  \begin{center}
    \includegraphics[width=0.80\textwidth]{screenshots/grafico/ss_tabuleiro_limpo.png}
  \end{center}
  \caption{O início de um jogo num tabuleiro de tamanho 3}
\end{figure}

\begin{figure}[h!]
  \begin{center}
    \includegraphics[width=0.80\textwidth]{screenshots/grafico/ss_tabuleiro_a_jogar.png}
  \end{center}
  \caption{Aspecto do tabuleiro com um jogo a decorrer}
\end{figure}

\begin{figure}[h!]
  \begin{center}
    \includegraphics[width=0.80\textwidth]{screenshots/grafico/ss_tabuleiro_final_popup.png}
  \end{center}
  \caption{Janela que aparece quando um jogo termina}
\end{figure}

\begin{figure}[h!]
  \begin{center}
    \includegraphics[width=0.80\textwidth]{screenshots/grafico/ss_tabuleiro_final_sem_popup.png}
  \end{center}
  \caption{Aspecto do tabuleiro no final do jogo}
\end{figure}

\begin{figure}[h!]
  \begin{center}
    \includegraphics[width=0.80\textwidth]{screenshots/cli/ss_cli_menu_inicial.png}
  \end{center}
  \caption{O menu inicial do programa quando corrido em modo de texto}
\end{figure}

\begin{figure}[h!]
  \begin{center}
    \includegraphics[width=0.80\textwidth]{screenshots/cli/ss_cli_tamanho_tabuleiro.png}
  \end{center}
  \caption{A interface para escolher o tamanho do tabuleiro em modo de
  texto}
\end{figure}

\begin{figure}[h!]
  \begin{center}
    \includegraphics[width=0.80\textwidth]{screenshots/cli/ss_cli_jogador_branco.png}
  \end{center}
  \caption{A interface para escolher a IA para o jogador branco em
    modo de texto}
\end{figure}

\begin{figure}[h!]
  \begin{center}
    \includegraphics[width=0.80\textwidth]{screenshots/cli/ss_cli_jogador_preto.png}
  \end{center}
  \caption{A interface para escolher a IA para o jogador preto em modo
    de texto}
\end{figure}

\begin{figure}[h!]
  \begin{center}
    \includegraphics[width=0.80\textwidth]{screenshots/cli/ss_cli_tabuleiro_limpo.png}
  \end{center}
  \caption{O inicio de um jogo num tabuleiro de tamanho 3 em modo de texto}
\end{figure}

\begin{figure}[h!]
  \begin{center}
    \includegraphics[width=0.80\textwidth]{screenshots/cli/ss_cli_tabuleiro_intermedio.png}
  \end{center}
  \caption{Aspecto do tabuleiro em modo de texto com um jogo a decorrer}
\end{figure}

\begin{figure}[h!]
  \begin{center}
    \includegraphics[width=0.80\textwidth]{screenshots/cli/ss_cli_fim_jogo.png}
  \end{center}
  \caption{Aspecto do tabuleiro em modo de texto no final do jogo}
\end{figure}

\end{document}
